package org.algorithm.wE1.数组.三月.第四周;

/**
 * @author zhx
 * @version 1.0
 * @date 2022/03/24 8:35 PM
 * @description:  周六
 *
 * url:  https://leetcode-cn.com/problems/search-rotate-array-lcci/
 */
public class 搜索旋转数组 {

    public static void main(String[] args) {
        int[] arr = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14};
        System.out.println(search(arr, 7));
    }


    public static int search(int[] arr, int target) {
        int n = arr.length;
        int result = -1;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r + 1) >> 1;
            if (arr[l] == target) return l;
            else if (arr[l] == arr[mid]) l++;
            else if (arr[l] < arr[mid]) {
                if (arr[l] > target || arr[mid] < target) l = mid;
                else {
                    l = l + 1;
                    r = mid;
                }
            } else {
                if (arr[l] > target && arr[mid] < target) l = mid;
                else {
                    l = l + 1;
                    r = mid;
                }
            }
        }
        return result;
    }
}
